Today's network links carry vast amounts of information. High bandwidth applications supported by these network links include, for example, streaming video, streaming audio, and large aggregations of voice traffic. In the future, network bandwidth demands are certain to increase.
As a business grows, so can its network, increasing in the number of network elements coupled to the network, the number of network links, and also geographic diversity. Over time, a business' network can include physical locations scattered throughout a city, a state, a country, or the world. Since it can be prohibitively expensive to create a private network that spans these great distances, many businesses opt to rely upon a third-party provider's network to provide connectivity between the disparate geographic sites of the business. In order for the business' network to seamlessly function through the provider network, the provider network must be able to provide a medium for transmission of all the business' various types of datastreams, including multicast transmission.
Multicast routing protocols enable multicast transmission (i.e., one-to-many connections and many-to-many connections) by replicating a multicast network packet close to the destination of that packet, obviating the need for multiple unicast connections for the same purpose; thus, saving network bandwidth and improving throughput. Upon receiving a multicast packet, a network node can examine a multicast group destination address (GDA) of the packet and determine whether one or more downstream subscribers to the multicast packet (i.e., members of the multicast group) are connected to the network node (either directly or indirectly). The network node can then replicate the multicast packet as needed and transmit the replicated packets to any connected subscribers.
FIG. 1A is a simplified block diagram of a network performing a multicast transmission. Network router elements 110, 120, 130 and 140 are coupled through network links 150, 160, and 170. Network router element 110 is also coupled to network elements 111 and 112; network router element 120 is coupled to network element 121; network router element 130 is coupled to network elements 131 and 132; and, network router element 140 is coupled to network element 141. Such coupling between the network router elements and the network elements can be direct or indirect (e.g., via a L2 network device or another network router element).
For the purposes of this illustration, network element 111 is a multicast source transmitting to a multicast group that includes network elements 112, 121, 131, 132 and 141. A multicast datastream having a group destination address to which the above network elements have subscribed as receiver members is transmitted from network element 111 to network router element 110 (illustrated by the arrow from 111 to 110). Network router element 110 determines where to forward packets in the multicast datastream by referring to an internal address table that identifies each port of network router element 110 that is coupled, directly or indirectly, to a subscribing member of the multicast group. Network router element 110 then replicates packets of the multicast datastream and then transmits the packets from the identified ports to network element 112, network router element 120 and network router element 130.
Network router elements 120 and 130 can inform network router element 110 that they are coupled to a subscribing member of a multicast datastream using, for example, a protocol independent multicast (PIM) multicast message. Using PIM, network router elements 120 and 130 can send messages indicating that they need to join (a “JOIN” message) or be excluded from (a “PRUNE” message) receiving packets directed to a particular multicast group or being transmitted by a particular source. Similarly, a network element can inform a first-hop network router element that the network element wishes to be a subscriber to a multicast group by sending a membership report request through a software protocol such as internet group management protocol (IGMP). When a network element wishes to subscribe to a multicast transmission, a special IGMP protocol frame can be transmitted as a multicast “JOIN” request. An IGMP-enabled network router element (or a L2 network device) can have “snooping” software executing to read such a frame and build a corresponding entry in a multicast group address table.
Upon receipt by network router elements 120 and 130, packets from the multicast datastream will be replicated as needed by those network router elements to provide the multicast datastream to network elements coupled to those network router elements (e.g., network elements 131 and 132 or network router element 140). In this manner, a multicast datastream from network element 111 can be transmitted through a network to multiple receiving network elements. The path of such a transmission can be thought of as a tree, wherein network element 111 is the root of the tree and network elements 121, 131, 132, and 141 can be thought of as the tips of branches.
FIG. 1B is a simplified block diagram of a network in which multiple sources are transmitting to a multicast group. As in FIG. 1A, network element 111 is a source for a multicast datastream directed to a multicast group including network elements 112, 121, 131, 132, and 141. That multicast datastream is illustrated by path 180 (a solid line). Network element 132 is also transmitting a multicast datastream to the multicast group, and that datastream is illustrated by path 190 (a dashed line). In a multiple source multicast group, any subscriber network element can be a source. In order to provide this two-way routing of multicast data packets, a bi-directional version of protocol independent multicast (PIM bidir) is used to configure the network router elements in the multicast tree. In such bi-directional multicast, datastream packets are routed only along the shared bi-directional tree, which is rooted at a rendezvous point for the multicast group, rather than at a particular datastream source. Logically, a rendezvous point is an address (e.g., a network router element) that is “upstream” from all other network elements. Passing all bi-directional multicast traffic through such a rendezvous point, establishes a loop-free tree topology with a root at the rendezvous point.
FIGS. 1A and 1B illustrate transmission of multicast datastreams in a network in which the network router elements 110, 120, 130 and 140 are directly coupled with one another. But, as stated above, as a business and its network grow, a business' network can become geographically diverse, and therefore the path over which the datastream must flow can include an intervening third-party provider network.
FIG. 2 is a simplified block diagram illustrating a network configuration in which geographically diverse subnets of a business' network are coupled through a third-party provider network. The business' network includes network router elements 210, 220, 230, and 240, wherein network router element 210 is coupled to network elements 211 and 212, network router element 220 is coupled to network element 221, network router element 230 is coupled to network elements 231 and 232, and network router element 240 is coupled to network element 241. In order to connect to the providers' network, a network router element on the edge of the business' network (a customer edge router) is coupled to a network router element on the edge of the provider's network (a provider edge router). In FIG. 2, customer edge router elements 250(1-3) are coupled to provider edge router elements 260(1-3), respectively. Network router element 240 is coupled to provider edge router element 260(4) (that is, network router element 240 is configured as a customer edge router).
It should be noted that the customer edge router and the provider edge router functionality can be provided by a single router. Further, a network router element such as 240 can also serve as an edge router. The provider edge routers provide access to the provider's network which can contain data transmission lines, network router elements, and OSI Level 2 network devices to aid in the transmission of data from one provider edge router to another provider edge router. The provider network illustrated in FIG. 2 contains, as an example, network router elements 270(1-5) and 270(r), which are coupled in a manner to permit transmission of packets through the provider network. A provider network is not limited to such a configuration, and can include any number of network router elements, transmission lines, and other L2 and L3 network devices.
In order to facilitate transmission of data through the provider network, the provider network can utilize different protocols from those used in coupled customer networks. Such provider network protocols can permit faster data transmission and routing through the network. Any needed translation between customer and provider network protocols can be performed by the edge routers. One such routing protocol that can be used by a provider network is multiprotocol label switching (MPLS).
In a typical router-based network, OSI Layer 3 packets pass from a source to a destination on a hop-by-hop basis. Transit routers evaluate each packet's Layer 3 header and perform a routing table lookup to determine the next hop toward the destination. Such routing protocols have little, if any, visibility into the network's OSI Layer 2 characteristics, particularly in regard to quality of service and link load.
To take such Layer 2 considerations into account, MPLS changes the hop-by-hop paradigm by enabling edge routers to specify paths in the network based on a variety of user-defined criteria, including quality of service requirements and an application's bandwidth needs. That is, path selection in a router-only network (Layer 3 devices) can now take into account Layer 2 attributes. In light of this dual nature, MPLS routers are called label switch routers (LSRs).
In an MPLS network, incoming datastream packets are assigned a label by an edge label switch router (e.g, provider edge router element 260(1)). An edge LSR has one or more network interfaces connected to other LSRs within the provider network and one or more other network interfaces connected to non-MPLS enabled devices (e.g., a customer edge router). The label takes the form of a header created by the edge LSR and used by LSRs within the provider network to forward packets. An LSR will create and maintain a label forwarding information base (LFIB) that indicates where and how to forward packets with specific label values. The LSRs that are within a provider's network (non-edge LSRs) are commonly called core LSRs, which switch labeled packets based on the label value in the label header. All interfaces of a core LSR are connected to other LSRs (either core or edge). The path defined by the labels through core LSRs between a pair of edge LSRs is called a label switch path (LSP). Label information is distributed among the LSRs through the use of a label distribution protocol (LDP). Packets are forwarded within the core network along the label switch path where each LSR makes forwarding decisions based solely on the contents of the label. At each hop, an LSR may strip off the existing label and apply a new label which tells the next hop how to forward the packet.
FIG. 3 is a simplified block diagram illustrating a path a datastream can take through an MPLS network. In FIG. 3, a series of LSRs (edge and core) interconnect, forming a physical path between two network elements, 390 and 395, which are connected to the MPLS network through customer edge routers 370 and 380. An Ethernet frame carrying an IP datagram generated by network element 390 will follow the standard Ethernet format with a normal Layer 2 header followed by a Layer 3 header. Because the destination address resides in a different network, customer edge router 370 forwards a packet including the IP datagram to edge LSR 310. Edge LSR 310 references its internal forwarding table (also known as a forwarding information base (FIB)) and determines that it needs to forward a packet including the IP datagram via interface 310(2) toward edge LSR 20.
The core of the MPLS network includes core LSRs 330, 340, 350, 360, which are coupled, directly or indirectly, to edge LSRs 310 and 320.
The FIB entry for the destination network in ingress edge LSR 310 indicates that edge LSR 310 must include a label with the packet to indicate what path the packet should take on its way to egress edge LSR 320 and from there to destination network element 395. The label can be inserted before the Layer 3 header in the frame passed from edge LSR 310 to the next hop core LSR 350. Core LSR 350 receives the frame at interface 350(1) and determines the presence of the label. Core LSR 350 then treats the packet according to the configuration in its label forwarding information base (LFIB), which directs the core LSR to forward the packet via interface 350(3) and to replace the old incoming label with a new outgoing label. Core LSR 360 will then handle the packet in a similar manner, receiving the packet at interface 360(1) and transmitting the packet via interface 360(4), after having stripped the label added at core LSR 350 and inserting a new label.
Edge LSR 320 is the egress point from the MPLS network for the packet. Edge LSR 320 performs a label lookup in the same way as the previous LSRs, but will have no outgoing label to use. Edge LSR 320 will then strip off all label information and pass a standard packet including the IP datagram to customer edge router 380, which will then transmit the IP frame to network element 395. It should be noted that the LSP between edge LSRs 310 and 320 can take different links than the ones indicated in FIG. 3. The table below illustrates the incoming and outgoing interface and incoming and outgoing label changes that occur at each LSR in the illustrated LSP.
TABLE 1IncomingIncomingDestinationOutgoingOutgoingRouterLabelInterfaceNetworkInterfaceLabel310—310(e0)B310(2)63506350(1)B350(3)1136011360(1)B360(4)73207320(2)B320(e0)—
A non-MPLS router makes a forwarding decision based on reading a Layer 3 destination address carried in a packet header and then comparing all or part of the Layer 3 address with information stored in the forwarding information base (FIB) maintained by the router. The non-MPLS router constructs the FIB using information the router receives from routing protocols. To support destination-based routing with MPLS, an LSR also is configured to use routing protocols and construct the LFIB using information the LSR receives from these protocols. An LSR must distribute, receive, and use allocated labels for LSR peers to correctly forward the frame. LSRs distribute labels using a label distribution protocol (LDP). A label binding associates a destination subnet with a locally significant label (see, e.g., Table 1). Labels are “locally significant” because they are replaced at each hop. Whenever an LSR discovers a neighbor LSR, the two LSRs establish a connection to transfer label bindings.
LDP can exchange subnet/label bindings using one of two methods: downstream unsolicited distribution or downstream-on-demand distribution. Downstream unsolicited distribution disperses labels if a downstream LSR needs to establish a new binding with its neighboring upstream LSR. In downstream-on-demand distribution, a downstream LSR sends a binding upstream only if the upstream LSR request it. For each router in an upstream LSR's route table, the upstream LSR identifies the next hop for that route. The upstream LSR then issues a request (via LDP) to the downstream (next hop) LSR for a label binding corresponding to the downstream LSR. When the downstream LSR receives the request, the downstream LSR allocates a label, creates an entry in its LFIB with the incoming label set to the newly allocated label, and then the downstream LSR returns a binding between the newly allocated label and the route to the upstream LSR that sent the original request. When the upstream LSR receives the binding information, the upstream LSR creates an entry in its LFIB and sets the outgoing label in the entry to the value received from the downstream LSR. In a network using downstream-on-demand distribution, this process is repeated recursively until the destination is reached.
When an LSR receives a packet with a label, the LSR uses the label for an index search in the LSR's LFIB. Each entry in the LFIB may consist of an incoming label (the LFIB index) and one or more subentries of the form: outgoing label, outgoing interface, and outgoing link-level information. If the LSR finds an entry with the incoming label equal to the label carried in the packet, for each component in the entry, the LSR replaces the label in the packet with the outgoing label, replaces link level information (such as the MAC address) in the packet with the outgoing link-level information, and forwards the packet over the outgoing interface. This forwarding decision uses an exact-match algorithm using a fixed-length, fairly short (as composed to an L3 address) label as an index. Such a simplified forwarding procedure enables a higher forwarding performance, and can be implemented in LSR hardware rather than software. A forwarding decision is further independent of the label's forwarding granularity; that is the same forwarding algorithm applies to both unicast and multicast. A unicast LFIB entry will have one outgoing label, outgoing interface and outgoing link level information. A multicast entry can have one or more outgoing labels, outgoing interfaces, and outgoing link-level informations associated with the one label.
Multicast transmission through a MPLS network can result in multiple egress edge LSRs receiving a datastream entering the MPLS network at a single ingress edge LSR. Such a point-to-multipoint label switch path through an MPLS network has a similar form to the multicast tree discussed above, wherein the route of the point-to-multipoint LSP tree is through the ingress edge LSR. But MPLS and LDP do not allow for configuration of a multipoint-to-multipoint label switch path, and therefore bi-directional multicast can only be performed by configuring multiple point-to-multipoint LSPs from each ingress edge LSR coupled to a source to the various egress edge LSRs. Such a process is costly in terms of configuration, time, flexibility, and memory/label space resources on the LSRs within the MPLS network. What is therefore needed is a means for configuring and maintaining a multipoint-to-multipoint LSP tree within a provider network using a protocol such as MPLS.